☆ Comptage de chaînes : preuve de la propriété - Vers le supérieur

Propriété Nombre de chaînes de longueur  `k` qui relient le sommet  `i` au sommet `j`

Soit  `n` et  \(k\) deux entiers naturels non nuls, et  \(A\) la matrice d’adjacence d’un graphe  \(G\) d’ordre  \(n\) dont les sommets sont numérotés de  \(1\) à \(n\) , puis rangés dans l’ordre croissant de leurs numéros.
𝑀 est une matrice carrée de taille \(n\times n\) .

Le coefficient de la  \(i\) -ème ligne et de la  \(j\) -ème colonne de la matrice  \(A^k\) donne le nombre de chaînes (ou de chemins) de longueur  \(k\) reliant le sommet  \(i\) au sommet \(j\) .

On appellera \(a^{(k)}_{ij}\)  le coefficient de la  \(i^{ieme}\) ligne et de la  \(j^{ieme}\) colonne de la matrice  \(A^k\) (attention, dans l’écriture \(a^{(k)}_{ij}\) , \((k)\)  n’est pas un exposant mais indique qu’on parle de la matrice \(A^k\) ).

Posons  \(P(k)\) la propriété : « Pour tout entier \(i\) ,  \(1\le i\le n\) et tout entier \(j\) , \(1\le j\le n\) , le coefficient  \(a^{(k)}_{ij}\) de la  \(i\) -ème ligne et de la \(j\) -ème colonne de la matrice  \(A^k\) donne le nombre de chaînes (ou de chemins) de longueur  \(k\) reliant le sommet  \(i\) au sommet  \(j\) . »

Démonstration

On va démontrer par récurrence que  \(P(k)\) est vraie pour tout  \(k \in \mathbb{N}^*\) .

Initialisation 
\(P(1)\) est vraie car  \(A^1=A\) et c’est la définition de la matrice d’adjacence.

Hérédité
Soit  \(k \in \mathbb{N}^*\) tel que  \(P(k)\) est vraie, a-t-on aussi \(P(k + 1)\) est vraie ?
Soit  \(i_0\) et  \(j_0\) deux entiers compris entre  \(1\) et \(n\) .
On veut compter le nombre de chaînes de longueur \(k + 1\)   reliant le sommet numéroté  \(i_0\) au sommet numéroté \(j_0\) .
Une telle chaîne est composée de \(k\) arêtes reliant le sommet numéroté  \(i_0\) à un autre sommet numéroté  \(p\) (avec \(1\le p\le n\) ) et d’une dernière arête reliant le sommet numéroté \(p\) au sommet numéroté \(j_0\) .
Or, d’après l’hypothèse de récurrence, le nombre de chaînes de longueur \(k\) reliant le sommet numéroté  \(i_0\) au sommet numéroté  \(p\) est égal à  \(a^{(k)}_{i_0p}\) .
De plus, le nombre de chaînes de longueur  \(1\) reliant le sommet numéroté  \(p\) au sommet numéroté  \(j_0\) est égal à \(a_{pj_0}=a^{(1)}_{pj_0}\)  par définition de la matrice d’adjacence.
Pour dénombrer ces chaînes, on doit donc sommer les termes  \(a^{(k)}_{i_op}\times a_{pj_0}\) pour  \(p\) allant de  \(1\) à \(n\) .
D’après la définition du produit de matrices,  \(\displaystyle\sum_{p=1}^n a^{(k)}_{i_op}\times a_{pj_0}=a^{(k+1)}_{i_0j_0}\) .
On a donc prouvé que, si \(P(k)\)  est vraie, alors \(P(k+1)\)  est vraie. La propriété est héréditaire.

Conclusion
Cette propriété est initialisée au rang 1 et héréditaire à partir de ce rang, elle est donc vraie pour tout \(k \in \mathbb{N}^*\) .